package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;

public class NC46_2 {
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
         Arrays.sort(num);
         dfs(num, 0, 0, new ArrayList<>(), target);
        String last = "", cur = null;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = queue.poll();
            cur = "";
            for (int e: list) {
                cur += ("_" + e);
            }
            if (!last.equals(cur)) {
                res.add(list);
            }
            last = cur;
        }
        return res;
    }
    
   Map<ArrayList<Integer>, Integer> set = new HashMap<>();
   Queue<ArrayList<Integer>> queue = new PriorityQueue<>((l1, l2) -> {
       int len = l1.size() < l2.size() ? l1.size() : l2.size();
       for (int i = 0; i < len; i++) {
           if (l1.get(i) != l2.get(i)) {
                return l1.get(i) - l2.get(i);
           }
       }
       return 0;
   });
    
    public void dfs(int[]nums, int idx,int sum, ArrayList<Integer> cur, int target) {
        if (idx == nums.length) {
            if (sum == target)
                queue.offer(new ArrayList<>(cur));
            return;
        }
        if (sum == target) {
            queue.offer(new ArrayList<>(cur));
            return;
        }
        if (sum + nums[idx] <= target) {
            cur.add(nums[idx]);
            dfs(nums, idx + 1, sum + nums[idx], cur, target);
            cur.remove(cur.size() - 1);
            dfs(nums, idx + 1, sum, cur, target);
        }
    }
}

@Test
public void test() {
    Solution s = new Solution();
    int[] nums = new int[]{100,10,20,70,60,10,50};
    ArrayList<ArrayList<Integer>> res = s.combinationSum2(nums, 80);
    System.out.println(res);
    
}
}
